' ====================================================
' Small Basic LP Cheapest Recipe
'
' This version: attempt to adapt version 1.0 to the case of CALCULATION
' OF CHEAPEST RECIPE
'
' Version 3.0 - Date 11 January 2023 (Reviewed 10 September 2026)
' > implements an example by David Lippman & Melonie Rasmussen
' > The method applied is described here:
' > https://www.zweigmedia.com/tutsM/tutSimplex.php?lang=en&ed=7
'
' http://smallbasic.com/program/?WQGP298.000
'
' ====================================================
' LINEAR PROGRAMMING TECHNIQUE
' From an excercise by David Lippman & Melonie Rasmussen
' The problem was exemplified here
' https://math.libretexts.org/Courses/Highline_College/Math_111%3A_College_Algebra/03%3A_Linear_Programming/3.05%3A_Applications_of__Linear_Programming
' The algorithm is described here
' https://math.libretexts.org/Courses/Highline_College/Math_111%3A_College_Algebra/03%3A_Linear_Programming/3.04%3A_Simplex_Method
' The method applied is described here:
' https://www.zweigmedia.com/tutsM/tutSimplex.php?lang=en&ed=7
'
' This program is based on the excellent explanations available in:
' Explanations from IMSE Concept Library | Laurel Nichols & Gina Christofaro | Spring 2015
' https://www.imse.iastate.edu/files/2015/08/Explanation-of-Simplex-Method.docx
' but solving a more complex scenario required a thprough reding of:
' https://www.zweigmedia.com/tutsM/tutSimplex.php?lang=en&ed=7
'
' Ported in Small Basic by Cesare Brizio
' (www.cesarebrizio.it)
' ---------------------------------------------------------
' THE CHEAPEST RECIPE PROBLEM
' ---------------------------------------------------------
' Since the end of the 1960's, my father was a pioneer in the application of
' computers to the automation of animal feed factories.
' With his undisputed intelligence, he most probably designed his algorithms
' from scratch. But it's a possibility that he studied linear algorithms.
' (https://en.wikipedia.org/wiki/Linear_programming)
' in which linear equality and linear inequality constraints become metaphors
' of real-world problems. In actuality, the definition of a "closed feasible
' region' of a problem is performed on geometrical terms.
' The Simplex algorithm was devised by George Dantzig in 1947, so it's a
' candidate influencer of my father's methods.
' -----------------------------------------------------------------------------------------
' In this case, that closely resembles the problems solved by my father,
' the target is to provide the cheapest possible mixture of ingredients,
' that grants the presence of a given proportion of substances.
' Base ingredients have different prices and contain the required substances.
' The proportions of substances present in each ingredient differ from both
' those required for the final mixture, and those of other ingredients.
' ====================================================
CRLF = Text.GetCharacter(13) + Text.GetCharacter(10)
Message = Message + "This program is just an algorithm demonstrator."+CRLF
Message = Message + "Please see comments in the heading of the source"+CRLF
Message = Message + "code for more details."+CRLF
Message = Message + "Values are hard-coded and no user interface is"+CRLF
Message = Message + "provided."+CRLF
Message = Message + "An effective application should be parametric"+CRLF
Message = Message + "and include provisions to design the objective"+CRLF
Message = Message + "functions and the constraints. Plus, in a"+CRLF
Message = Message + "real-world scenario, it would be advisable"+CRLF
Message = Message + "to store in a database all the data such as"+CRLF
Message = Message + "the recipes and the nutritional constraints."+CRLF
Message = Message + "--------------------------------------------"+CRLF
Message = Message + "A minimal effort has been put in using arrays"+CRLF
Message = Message + "to store the values needed for the problem and"+CRLF
Message = Message + "its solution. Those arrays may simulate simple"+CRLF
Message = Message + "database tables and inspire the design of an"+CRLF
Message = Message + "actual RDBMS for nutritional constraints,"+CRLF
Message = Message + "ingredient composition and actual recipes."+CRLF
Message = Message + "--------------------------------------------"+CRLF
Message = Message + "In other words, the design of the Simplex"+CRLF
Message = Message + "Tableau should be entrely automated, with as"+CRLF
Message = Message + "many colums as needed to cover the nutritional"+CRLF
Message = Message + "constraints of any recipe and the composition"+CRLF
Message = Message + "of each ingredient."+CRLF
Message = Message + "Feel free to improve this sketch as needed!"+CRLF
'GraphicsWindow.ShowMessage(Message,"LINEAR PROGRAMMING EXAMPLE")
Message = "============================================"+CRLF
Message = "================> EXERCISE <================"+CRLF
Message = "============================================"+CRLF
Message = "A company is creating a meal replacement bar."+CRLF
Message = Message + "They plan to incorporate peanut butter,"
Message = Message + "oats, and dried cranberries asthe primary ingredients."
Message = Message + "The nutritional content of 10 grams of each is listed "
Message = Message + "below, along with the cost, in cents, of each ingredient."
Message = Message + "Find the amount of each ingredient they should use to"
Message = Message + "minimize the cost of producing a barcontaining a "
Message = Message + "minimum of 15g of each ingredient, at least 10g"
Message = Message + "of protein and at most 14g of fat."+CRLF
Message = Message + ""+CRLF
Message = Message + "Current implementation has no user interface, you are"
Message = Message + "welcome to improve it anytime. Values are hard-coded into"
Message = Message + "variables and you can change them by intervening"
Message = Message + "on the source code."+CRLF
Message = Message + ""+CRLF
Message = Message + "CONTENTS OF 10 GRAMS OF INGREDIENT"+CRLF
Message = Message + "----------------------------------"+CRLF
Message = Message + "PEANUT BUTTER, Proteins 2.5g (Ppb) - Fat 5g(Fpb)"+CRLF
Message = Message + "OATS, Proteins 1.7g (Po) - Fat 0.7g (Fo)"+CRLF
Message = Message + "CRANBERRIES, Proteins 0g (Pc)- Fat 0.1g (Fc)"+CRLF
Message = Message + ""+CRLF
Message = Message + "COST OF ONE SERVING (=10 GRAMS) OF INGREDIENT"+CRLF
Message = Message + "----------------------------------"+CRLF
Message = Message + "PEANUT BUTTER, 6 cent (Cp)"+CRLF
Message = Message + "OATS, 1 cent (Co)"+CRLF
Message = Message + "CRANBERRIES, 2 cent (Cc)"+CRLF
Message = Message + ""+CRLF
Message = Message + "=============================================="+CRLF
Message = Message + " FORMAL DESCRIPTION OF THE PROBLEM"+CRLF
Message = Message + "=============================================="+CRLF
Message = Message + " MINIMIZE COST = 6Cp + 1Co + 2Cc"+CRLF
Message = Message + " Subject to:"+CRLF
Message = Message + " 2.5Ppb + 1.7Po + 0Pc >= 10 (at least 10g of protein)"+CRLF
Message = Message + " 5Ppb + 0.7Po + 0.1Pc <= 14 (no more than 14g of fat)"+CRLF
Message = Message + " Ppb >= 1.5 (at least 15g of Peanut Butter)"+CRLF
Message = Message + " Po >= 1.5 (at least 15g of Oats)"+CRLF
Message = Message + " Pc >= 1.5 (at least 15g of Cranberries)"+CRLF
Message = Message + "=============================================="+CRLF
Message = Message + " SOLUTION"+CRLF
Message = Message + "=============================================="+CRLF
Message = Message + "COST = 15.6765" +CRLF
Message = Message + "Ppb = 1.5 (15 grams)" +CRLF
Message = Message + "Po = 3.67647 (36,8 grams)" +CRLF
Message = Message + "Pc = 1.5 (15 grams)"+CRLF
Message = Message + ""+CRLF
Message = Message + "Interpreting that result, the minimum cost to produce"
Message = Message + "the bar will be about 15 cents, by using 15 grams of"
Message = Message + "peanut butter, 36.8 grams of oats, and 15 grams of "
Message = Message + "dried cranberries. Verifying our conditions, we can"
Message = Message + "see that our recipe contains at least 15g of each"
Message = Message + "ingredient."+CRLF
Message = Message + "The protein content will be around 10g"+CRLF
Message = Message + "(2.5*1.5)+(1.7*3.68)+(0*1.5)"+CRLF
Message = Message + "The fat content will be around 10.15g"+CRLF
Message = Message + "(5*1.5)+(0.7*3.68)+(0.1*1.5)"+CRLF
Message = Message + ""
'GraphicsWindow.ShowMessage(Message,"LINEAR PROGRAMMING EXAMPLE")
'----------------------------------------------------
' NAMES OF INGREDIENTS
'----------------------------------------------------
NUM_INGREDIENTS = 3
ING_NAMES[1] = "PEANUT BUTTER"
ING_NAMES[2] = "OATS"
ING_NAMES[3] = "CRANBERRIES"
'----------------------------------------------------------------------
' COST PER ONE SERVING (10 g) OF INGREDIENTS in cents
' TOTAL COST is the OBJECTIVE FUNCTION to minimize
'----------------------------------------------------------------------
ING_COST[1] = 6
ING_COST[2] = 1
ING_COST[3] = 2
'----------------------------------------------------
' OBJECTIVE FUNCTION
'----------------------------------------------------
'
' MINIMIZE COST = 6Cp + 1Co + 2Cc
'
' translated into
'
' MAXIMIZE -COST = -6Cp - 1Co - 2Cc
'
' Ingredients are the three variables in
' the constraints and in the objective
' function
OBJECTIVE_FUNCTION_SIGN = 1 ' will be used more under
'==============================================
' CONSTRAINTS
' One row per constraint
' One column per ingredient
' Last columns are the condition sign
' (all the condition must be equal, so a >=
' condition can be changed to <= by
' multiplying it by -1) and the last column
' is the required value. Indexing is
' Constraint[Constraint][component value]
' Constraint[Constraint][4] contains the value of the constraint
'==============================================
NUM_CONSTRAINTS = 5
'===========================================
' CONSTRAINT 1 is "PROTEIN CONTENT"
' 2.5Ppb + 1.7Po + 0Pc >= 10 (at least 10g of protein)
'===========================================
Constraint_description[1] = "MINIMUM GRAMS OF PROTEIN REQUIRED "
Constraint_sign[1] = -1 ' More-than-or-equal-to inequality requires NEGATIVE slack variable
Constraint[1][1] = 2.5 'Peanut Butter
Constraint[1][2] = 1.7 'Oats
Constraint[1][3] = 0 'Cranberries
Constraint[1][4] = 10
'===========================================
' CONSTRAINT 2 is "FAT CONTENT"
' 5Ppb + 0.7Po + 0.1Pc <= 14 (no more than 14g of fat)"
'===========================================
Constraint_description[2] = "MAXIMUM GRAMS OF FAT REQUIRED "
Constraint_sign[2] = 1 ' Less-than-or-equal-to inequality requires POSITIVE slack variable
Constraint[2][1] = 5 'Peanut Butter
Constraint[2][2] = 0.7 'Oats
Constraint[2][3] = 0.1 'Cranberries
Constraint[2][4] = 14
'===========================================
' SERVING SIZE
' 10 grams per "serving" - the quantity of ingredient on which the quantity
' of nutrients (proteins and fat) and the COST is based, e.g. "0,7 grams fat"
' for oats and "6 cents per serving" for peanut butter".
' For consistency, the constraints about both the quantity of each ingredient
' and its cost shall be expressed in SERVINGS, because both the quantity of
' nutrients and the cost refer to a serving, not to a gram.
'===========================================
Serving_Size = 10 'number of grams in a serving
'===========================================
' CONSTRAINT 3 is "AT LEAST 15g OF PEANUT BUTTER"
' 1Ppb + 0Po + 0Pc >= 1.5 (at least 15g of Peanut Butter)"
'===========================================
Constraint_sign[3] = -1 ' More-than-or-equal-to inequality requires NEGATIVE slack variable
Constraint[3][1] = 1 'Peanut Butter
Constraint[3][2] = 0 'Oats
Constraint[3][3] = 0 'Cranberries
Constraint[3][4] = 1.5 'required quantity (servings) of the ingredient whose constraint 3 column equals 1
'===========================================
' CONSTRAINT 4 is "AT LEAST 15g OF OATS"
' 0Ppb + 1Po + 0Pc >= 1.5 (at least 15g of Oats)"
'===========================================
Constraint_sign[4] = -1 ' More-than-or-equal-to inequality requires NEGATIVE slack variable
Constraint[4][1] = 0 'Peanut Butter
Constraint[4][2] = 1 'Oats
Constraint[4][3] = 0 'Cranberries
Constraint[4][4] = 1.5 'required quantity (servings) of the ingredient whose constraint 4 column equals 1
'==============================================
' CONSTRAINT 5 is "AT LEAST 15g OF DRIED CRANBERRIES"
' 0Ppb + 0Po + 1Pc >= 1.5 (at least 15g of Cranberries)"
'==========================================)====
Constraint_sign[5] = -1 ' More-than-or-equal-to inequality requires NEGATIVE slack variable
Constraint[5][1] = 0 'Peanut Butter
Constraint[5][2] = 0 'Oats
Constraint[5][3] = 1 'Cranberries
Constraint[5][4] = 1.5 'required quantity (servings) of the ingredient whose constraint 5 column equals 1
'========================================
' Four arrays that will help debug and result visualization
'========================================
COLUMN_NAME[1] = "X" ' PEANUT BUTTER"
COLUMN_NAME[2] = "Y" ' OATS"
COLUMN_NAME[3] = "Z" ' CRANBERRIES"
COLUMN_NAME[4] = "S1" ' "SLACK VARIABLE 1"
COLUMN_NAME[5] = "S2" ' "SLACK VARIABLE 2"
COLUMN_NAME[6] = "S3" ' "SLACK VARIABLE 3"
COLUMN_NAME[7] = "S4" ' "SLACK VARIABLE 4"
COLUMN_NAME[8] = "S5" ' "SLACK VARIABLE 5"
COLUMN_NAME[9] = "C" ' "OBJECTIVE FUNCTION VALUE (COST)"
COLUMN_NAME[10] = "BETA"
COLUMN_FULL_NAME[1] = "Grams per bar, PEANUT BUTTER "
COLUMN_FULL_NAME[2] = "Grams per bar, OATS "
COLUMN_FULL_NAME[3] = "Grams per bar, DRIED CRANBERRIES "
COLUMN_FULL_NAME[4] = "SLACK VARIABLE 1"
COLUMN_FULL_NAME[5] = "SLACK VARIABLE 2"
COLUMN_FULL_NAME[6] = "SLACK VARIABLE 3"
COLUMN_FULL_NAME[7] = "SLACK VARIABLE 4"
COLUMN_FULL_NAME[8] = "SLACK VARIABLE 5"
COLUMN_FULL_NAME[9] = "COST PER BAR (cents) "
COLUMN_FULL_NAME[10] = "BETA COLUMN "
SHOW_RESULT[1] = "True"
SHOW_RESULT[2] = "True"
SHOW_RESULT[3] = "True"
SHOW_RESULT[4] = "False"
SHOW_RESULT[5] = "False"
SHOW_RESULT[6] = "False"
SHOW_RESULT[7] = "False"
SHOW_RESULT[8] = "False"
SHOW_RESULT[9] = "True"
SHOW_RESULT[10] = "False"
RESULT_MULTIPLIER[1] = Serving_Size 'result will be the number of 10 grams servings
RESULT_MULTIPLIER[2] = Serving_Size 'result will be the number of 10 grams servings
RESULT_MULTIPLIER[3] = Serving_Size 'result will be the number of 10 grams servings
RESULT_MULTIPLIER[4] = 1
RESULT_MULTIPLIER[5] = 1
RESULT_MULTIPLIER[6] = 1
RESULT_MULTIPLIER[7] = 1
RESULT_MULTIPLIER[8] = 1
RESULT_MULTIPLIER[9] = -1 'result will be negative due to the initial sign reversal
RESULT_MULTIPLIER[10] = 1
'========================================
' STANDARD FORM
'========================================
'(1) must be a maximization problem,
'(2) all linear constraints must be in a less-than-or-equal-to inequality,
'(3) all variables are non-negative.
'
' To transform a minimization linear program model into
' a maximization linear program model, simply multiply both
' the left and the right sides of the objective function by -1.
' MINIMIZE COST = 6Cp + 1Co + 2Cc
' becomes
' MAXIMIZE COST = -6Cp - 1Co - 2Cc
'
' Transforming linear constraints from a greater-than-or-equal-to inequality
' to a less-than-or-equal-to inequality can be done similarly as what was done
' to the objective function. By multiplying by -1 on both sides, the inequality can
' be changed to less-than-or-equal-to.
'=========================================
'Constraint_sign[I] will be used For the slack variable
'=========================================
'========================================
' DETERMINE SLACK VARIABLES
'========================================
' Slack variables are additional variables that are introduced into the linear
' constraints of a linear program to transform them from inequality constraints
' to equality constraints. If the model is in standard form, the slack variables
' will always have a +1 coefficient. Slack variables are needed in the constraints
' to transform them into solvable equalities with one definite answer.
'
' THE SLACK VARIABLES WILL BE ADDED DURING
' THE CREATION OF THE TABLEAU
'========================================
' BUILD THE SIMPLEX TABLEAU
'========================================
' See http://pages.intnet.mu/cueboy/education/notes/algebra/simplex.htm#Example%201
' There is a tableau row for each condition, plus one tableau row
' for quantifying the objective function to be maximized/minimized
' In each row, there is one column for each variable (in our case,
' for each ingredient) plus the columns for "slack variables", whose number
' is equal to the number of constraints.
' The rightmost column is used to store the target values for the conditions
' defined in each line
' The last line contains the values of the objective function to maximize or minimize
'
'---------------------------------------
' As many rows, as conditions +1
'---------------------------------------
Vertical_Size_Tableau = NUM_CONSTRAINTS+1
'--------------------------------------------------------------
' As many columns, as double the ingredients +2
' (one slack variables per constraint and one total column are needed)
'---------------------------------------------------------------
Horizontal_Size_Tableau = (NUM_INGREDIENTS+NUM_CONSTRAINTS)+2
' initialize all tableau cells at 0
For I = 1 To Vertical_Size_Tableau
For J = 1 To Horizontal_Size_Tableau
Tableau[I][J]=0.000
EndFor
EndFor
'-------------------------------------------------------
' Fill the top left part of the simplex tableau
' One condition per row
' One ingredient per column (conditions are
' defined as proportions of ingredients)
'-------------------------------------------------------
For I = 1 To NUM_CONSTRAINTS
For J = 1 To NUM_INGREDIENTS
Tableau[I][J]=Constraint[I][J]
EndFor
EndFor
' DEBUG
'ShowSimplexTableau()
'TextWindow.WriteLine("Above, before putting slack variables in the tableau")
'TextWindow.Read()
'-------------------------------------------------------
' PUT SLACK VARIABLES IN THE TABLEAU
'-------------------------------------------------------
' put the slack variables as a diagonal line in front of the conditions
For I = 1 To NUM_CONSTRAINTS
For J = (NUM_INGREDIENTS+1) To Horizontal_Size_Tableau-1
Curr_Column = J-NUM_INGREDIENTS
If I = Curr_Column Then
Tableau[I][J]= Constraint_sign[I]
EndIf
EndFor
EndFor
'----------------------------------------------------------------------------
' Fill the last slack variable at the penultimate column
' of the last row with the objective function sign
'----------------------------------------------------------------------------
Tableau[Vertical_Size_Tableau][Horizontal_Size_Tableau-1] = OBJECTIVE_FUNCTION_SIGN
' DEBUG
'ShowSimplexTableau()
'TextWindow.WriteLine("Above, before putting constraint values in the tableau")
'TextWindow.Read()
'-------------------------------------------------------
' PUT CONSTRAINT VALUES IN THE LAST
' COLUMN OF THE TABLEAU
'-------------------------------------------------------
' Fill the last column of the simplex tableau
For I = 1 To NUM_CONSTRAINTS
Tableau[I][Horizontal_Size_Tableau] = Constraint[I][4]
EndFor
' DEBUG
'ShowSimplexTableau()
'TextWindow.WriteLine("Above, before putting objective functions coefficients in the tableau")
'TextWindow.Read()
'-------------------------------------------------------
' PREPARE A VECTOR FOR THE PIVOTED STATE
' FOR EACH COLUMN OF THE TABLEAU
'-------------------------------------------------------
For I = 1 To Horizontal_Size_Tableau
Already_Pivoted[I] = "False"
EndFor
'-------------------------------------------------------
' PUT THE OBJECTIVE FUNCTIONS
' COEFFICIENTS IN THE LAST LINE
' OF THE TABLEAU.
' THE VALUES SHOULD BE MULTIPLIED BY
' -1
'-------------------------------------------------------
' Fill with COEFFICIENTS the last line of the simplex tableau
For I = 1 To NUM_INGREDIENTS
Tableau[NUM_CONSTRAINTS+1][I] = ING_COST[I]
EndFor
'===============================================================================
' TABLEAU STRUCTURE
'===============================================================================
'Column Column Column Column Column Column Column Column Column Column
' 1 2 3 4 5 6 7 8 9 10
'
' Peanut Oats Cran- S1 S2 S3 S4 S5 (*) B
' Butter berries
'================================================================================
' Z or (*) - column of the value of the objective function
' B - the "Beta" column will contain optimal solutions for the basic variables
'================================================================================
' =======================================================================
' ADD STARS
' -------------------------------------------------------
' star all rows whose decision variables are negative to indicate that the current solution is not feasible
' the stars will be used to identify the PIVOT COLUMN in Phase 1
' =======================================================================
For I = 1 to NUM_CONSTRAINTS+1
If Constraint_sign[I] = -1 Then
STARRED[I] ="*" ' it is STARRED because it's NEGATIVE
Else
STARRED[I] =" "
EndIf
EndFor
ImageWidth=ImageList.GetWidthOfImage("C:\Users\cesar\Documents\Programmi Small Basic\Simplex Method\Explanations.png")
ImageHeight=ImageList.GetHeightOfImage("C:\Users\cesar\Documents\Programmi Small Basic\Simplex Method\Explanations.png")
GraphicsWindow.DrawResizedImage("C:\Users\cesar\Documents\Programmi Small Basic\Simplex Method\Explanations.png",0,50,Math.Round(ImageWidth*0.8),Math.Round(ImageHeight*0.8))
GraphicsWindow.Show()
'========================================
'========================================
'========================================
' PHASE 1 - GET RID OF THE STARS
'========================================
'========================================
'========================================
'========================================
' WHILE loops in Small basic are notoriously unreliable
' as any variable-based WHILE condition is checked
' only at the beginning of the loop.
' Reluctantly, I resort to a GoTo
'========================================
TABLEAU_NUMBER = 1
BEGIN_LOOP:
ShowSimplexTableau()
' ---------------------------------------------------------------------------------------------------
' The rule for the selecting a pivot column is this: Look at all the entries in the first
' starred row, excluding the last entry on the right (in the "answers" column).
' From these, choose the positive number with the largest magnitude; its column
' is the pivot column. If there are two or more candidates, choose any one. If there
' are no positive numbers to choose, that indicates that the feasible region is empty,
' and so the LP problem has no solution.
' ---------------------------------------------------------------------------------------------------
' CHOOSE PIVOT COLUMN
' by anlyzing the TOP STARRED row
' CHOOSE THE COLUMN WITH THE HIGHEST POSITIVE VALUE
' ===============================================
Most_Positive_Value = -9999 ' self-explanatory
Pivot_column = 0 ' self-explanatory
FIRST_STARRED_ROW = 0
' ===============================================
' FIND TOPMOST STARRED ROW
' ===============================================
For Constr = NUM_CONSTRAINTS To 1 Step -1
If STARRED[Constr] = "*" Then
FIRST_STARRED_ROW = Constr
EndIf
EndFor
If FIRST_STARRED_ROW = 0 Then
Goto EXIT_LOOP
EndIf
For i=1 To Horizontal_Size_Tableau-1
If Tableau[FIRST_STARRED_ROW][i] <> 0 Then
' The pivot column is the one with the most positive non-zero value
' ==========================================================
' CHOOSE THE NOT PIVOTED COLUMN WITH THE HIGHEST POSITIVE VALUE
' ==========================================================
If Tableau[FIRST_STARRED_ROW][i] > Most_Positive_Value And Already_Pivoted[I] = "False" Then
Most_Positive_Value = Tableau[FIRST_STARRED_ROW][i]
' Until proved otherwise, this is the most positive (=pivot) column
Pivot_column = i
EndIf
EndIf
EndFor
' --------------------------------------------------------------------------------------
' The algorithm should avoid processing a column twice.
' This variable was set as a security device
' --------------------------------------------------------------------------------------
Already_Pivoted[Pivot_column] = "True"
' DEBUG
'TextWindow.WriteLine("Pivot column chosen - "+Pivot_column)
'TextWindow.Read()
Least_Non_Negative_Ratio = 99999999999999 ' self-explanatory
'======================================
' CHOOSE PIVOT ROW
' by analyzing the last column
'look for the least non negative ratio (=pivot) row
'======================================
Pivot_row = 0 ' self-explanatory
For I = 1 To NUM_CONSTRAINTS
If Tableau[i][Pivot_column] > 0 Then
If Tableau[i][Horizontal_Size_Tableau] / Tableau[i][Pivot_column] < Least_Non_Negative_Ratio Then
Least_Non_Negative_Ratio = Tableau[i][Horizontal_Size_Tableau] / Tableau[i][Pivot_column]
' Until proved otherwise, this is the least non negative ratio (=pivot) row
Pivot_row = i
EndIf
EndIf
EndFor
' --------------------------------------------------------------------------------------
' REMOVE THE STAR FROM THE PIVOTED ROW
' --------------------------------------------------------------------------------------
STARRED[Pivot_row] = " "
'======================================
' The PIVOT ELEMENT is at the intersection of
' PIVOT ROW and PIVOT COLUMN
' Make 0 all the numbers above or below the pivot
' element by using basic row operations
'======================================
PIVOT_ELEMENT_VALUE = Tableau[Pivot_row][Pivot_column]
RECIPROCAL_P_E_V = (1 / PIVOT_ELEMENT_VALUE)
' DEBUG
'TextWindow.WriteLine("Pivot row chosen - "+Pivot_row+" - Press any key")
'TextWindow.WriteLine("Pivot element value = "+PIVOT_ELEMENT_VALUE+" - Press any key")
'TextWindow.Read()
'----------------------> SET TO ZERO ALL THE VALUES IN THE PIVOT COLUMN
'----------------------> EXCEPT THE PIVOT ELEMENT
For update_row = 1 To Vertical_Size_Tableau
If update_row <> Pivot_row Then
' The previous values of the pivot column now being overwritten are needed
' more under
OLD_VALUE_PIVOT_COLUMN[update_row] = Tableau[update_row][Pivot_column]
Tableau[update_row][Pivot_column] = 0
EndIf
EndFor
'----------------------> UPDATE THE ROW
For update_column = 1 To Horizontal_Size_Tableau
Tableau[Pivot_row][update_column] = Tableau[Pivot_row][update_column] * RECIPROCAL_P_E_V
EndFor
For update_row = 1 To Vertical_Size_Tableau
For update_column = 1 To Horizontal_Size_Tableau
' Here for any cell in the Tableau
If update_column <> Pivot_column Then
' Here for any cell in the Tableau outside the PIVOT COLUMN
If update_row <> Pivot_row Then
' Here for any non-zero cell in the Tableau outside the PIVOT COLUMN and the PIVOT ROW
' ===================================================================
' Explanations from IMSE Concept Library | Laurel Nichols & Gina Christofaro | Spring 2015
' ------------------------------------------------------------------------------------------------------------------
' In order to keep the tableau equivalent, the other variables not contained in the pivot column
' or pivot row must be calculated by using the new pivot values. For each new value, multiply
' the negative of the value in the old pivot column by the value in the new pivot row that
' corresponds to the value being calculated. Then add this to the old value from the old tableau
' to produce the new value for the new tableau.
' ===================================================================
' just for clarity, I store the current cell value in a variable
Curr_cell_value = Tableau[update_row][update_column]
' the new values from the pivot row are readily available. I select the one corrresponding
' to the current column
Value_new_pivot_row = Tableau[Pivot_row][update_column]
' the old values from the pivot column were saved beforehand. I select the one corrresponding
' to the current row, and change its sign
Neg_value_old_pivot_column = OLD_VALUE_PIVOT_COLUMN[update_row] * -1
' now the value for the new tableau cell can be assigned
Tableau[update_row][update_column]=(Neg_value_old_pivot_column * Value_new_pivot_row) + Curr_cell_value
EndIf
EndIf
EndFor
EndFor
TABLEAU_NUMBER = TABLEAU_NUMBER + 1
Goto BEGIN_LOOP
EXIT_LOOP:
TextWindow.WriteLine(" ")
TextWindow.WriteLine(" PHASE 1 COMPLETED - NO MORE STARRED ROWS")
TextWindow.Read()
'========================================
'========================================
'========================================
' PHASE 2 - COMPLETE OPTIMIZATION
'========================================
'========================================
'========================================
'========================================
' WHILE loops in Small basic are notoriously unreliable
' as any variable-based WHILE condition is checked
' only at the beginning of the loop.
'Reluctantly, I resort to a GoTo
'========================================
BEGIN_SECOND_LOOP:
'DEBUG
ShowSimplexTableau()
'---------- Pseudo-boolean for negative values in the bottom row
Neg_Val_Bottom_Line = "FALSE"
'======================================
' CHECK IF THE BOTTOM ROW CONTAINS
' NEGATIVE VALUES, IF NO NEGATIVE VALUE
' EXISTS THE TABLEAU IS OPTIMIZED
'======================================
For i=1 To Horizontal_Size_Tableau - 1
If Tableau[Vertical_Size_Tableau][i] < 0 Then
Neg_Val_Bottom_Line = "TRUE"
EndIf
EndFor
' Loop is terminated as soon as no negative values can be found in the
' left part of the bottom row
If Neg_Val_Bottom_Line = "FALSE" Then
Goto EXIT_SECOND_LOOP
EndIf
' DEBUG
'TextWindow.WriteLine("Neg_Val_Bottom_Line - "+ Neg_Val_Bottom_Line)
'TextWindow.Read()
'======================================
' CHOOSE PIVOT COLUMN
' by anlyzing the bottom row
' CHOOSE THE COLUMN WITH THE MOST NEGATIVE VALUE
'======================================
Most_Negative_Value = 0 ' self-explanatory
Pivot_column = 0 ' self-explanatory
For i=1 To Horizontal_Size_Tableau-1
If Tableau[Vertical_Size_Tableau][i] < 0 Then
' The pivot column is the one with the most negative value
If Tableau[Vertical_Size_Tableau][i] < Most_Negative_Value Then
Most_Negative_Value = Tableau[Vertical_Size_Tableau][i]
' Until proved otherwise, this is the most negative (=pivot) column
Pivot_column = i
EndIf
EndIf
EndFor
' --------------------------------------------------------------------------------------
' The algorithm should avoid processing a column twice.
' This variable was set as a security device and most probably is useless
' --------------------------------------------------------------------------------------
Already_Pivoted[Pivot_column] = "True"
' DEBUG
' TextWindow.WriteLine("Pivot column chosen - "+Pivot_column)
' TextWindow.Read()
Least_Non_Negative_Ratio = 99999999999999 ' self-explanatory
'======================================
' CHOOSE PIVOT ROW
' by analyzing the last column and looking for the
' LEAST NON NEGATIVE RATIO between the leftmost
' column "BETA" and each value in the column
'======================================
Pivot_row = 0 ' self-explanatory
For I = 1 To NUM_CONSTRAINTS
If Tableau[i][Pivot_column] > 0 Then
If Tableau[i][Horizontal_Size_Tableau] / Tableau[i][Pivot_column] < Least_Non_Negative_Ratio Then
Least_Non_Negative_Ratio = Tableau[i][Horizontal_Size_Tableau] / Tableau[i][Pivot_column]
' Until proved otherwise, this is the least non negative ratio (=pivot) row
Pivot_row = i
EndIf
EndIf
EndFor
'======================================
' The PIVOT ELEMENT is at the intersection of
' PIVOT ROW and PIVOT COLUMN
' Make 0 all the numbers above or below the pivot
' element by using basic row operations
'======================================
PIVOT_ELEMENT_VALUE = Tableau[Pivot_row][Pivot_column]
RECIPROCAL_P_E_V = (1 / PIVOT_ELEMENT_VALUE)
' DEBUG
'TextWindow.WriteLine("Pivot row chosen - "+Pivot_row+" - Press any key")
'TextWindow.WriteLine("Pivot element value = "+PIVOT_ELEMENT_VALUE+" - Press any key")
'TextWindow.Read()
'----------------------> SET TO ZERO ALL THE VALUES IN THE PIVOT COLUMN
'----------------------> EXCEPT THE PIVOT ELEMENT
For update_row = 1 To Vertical_Size_Tableau
If update_row <> Pivot_row Then
' The previous values of the pivot column now being overwritten are needed
' more under
OLD_VALUE_PIVOT_COLUMN[update_row] = Tableau[update_row][Pivot_column]
Tableau[update_row][Pivot_column] = 0
EndIf
EndFor
'----------------------> UPDATE THE ROW
For update_column = 1 To Horizontal_Size_Tableau
Tableau[Pivot_row][update_column] = Tableau[Pivot_row][update_column] * RECIPROCAL_P_E_V
EndFor
For update_row = 1 To Vertical_Size_Tableau
For update_column = 1 To Horizontal_Size_Tableau
' Here for any cell in the Tableau
If update_column <> Pivot_column Then
' Here for any cell in the Tableau outside the PIVOT COLUMN
If update_row <> Pivot_row Then
' Here for any non-zero cell in the Tableau outside the PIVOT COLUMN and the PIVOT ROW
' ===================================================================
' Explanations from IMSE Concept Library | Laurel Nichols & Gina Christofaro | Spring 2015
' ------------------------------------------------------------------------------------------------------------------
' In order to keep the tableau equivalent, the other variables not contained in the pivot column
' or pivot row must be calculated by using the new pivot values. For each new value, multiply
' the negative of the value in the old pivot column by the value in the new pivot row that
' corresponds to the value being calculated. Then add this to the old value from the old tableau
' to produce the new value for the new tableau.
' ===================================================================
' just for clarity, I store the current cell value in a variable
Curr_cell_value = Tableau[update_row][update_column]
' the new values from the pivot row are readily available. I select the one corrresponding
' to the current column
Value_new_pivot_row = Tableau[Pivot_row][update_column]
' the old values from the pivot column were saved beforehand. I select the one corrresponding
' to the current row, and change its sign
Neg_value_old_pivot_column = OLD_VALUE_PIVOT_COLUMN[update_row] * -1
' now the value for the new tableau cell can be assigned
Tableau[update_row][update_column]=(Neg_value_old_pivot_column * Value_new_pivot_row) + Curr_cell_value
EndIf
EndIf
EndFor
EndFor
TABLEAU_NUMBER = TABLEAU_NUMBER + 1
Goto BEGIN_SECOND_LOOP
EXIT_SECOND_LOOP:
'ShowSimplexTableau()
TextWindow.WriteLine(" ")
TextWindow.WriteLine(" PHASE 2 COMPLETED - NO MORE NEGATIVE VALUES IN COLUMS FROM X TO C IN THE LAST ROW")
TextWindow.WriteLine(" ")
TextWindow.WriteLine(" ====> EXPECTED RESULTS <=====")
TextWindow.WriteLine("Grams per bar, PEANUT BUTTER: Around 15")
TextWindow.WriteLine("Grams per bar, OATS: Around 37")
TextWindow.WriteLine("Grams per bar, DRIED CRANBERRIES: Around 15")
TextWindow.WriteLine("COST PER BAR (cents): Around 15.7 cents")
TextWindow.WriteLine("Grams, MINIMUM Protein content: 10")
TextWindow.WriteLine("Grams, MAXIMUM Fat content: 14")
TextWindow.WriteLine(" ")
TextWindow.Read()
TextWindow.WriteLine(" ====> ACTUAL RESULTS <=====")
'======================================================
' Identify solutions
'======================================================
'======================================================
' FIND BASIC VARIABLES - those having a single 1 in their column and the
' rest is all zeros. The solution is in the last ("Beta") column, in the row that
' contains a 1 in the basic variable column
'======================================================
For J = 1 to (Horizontal_Size_Tableau-1)
Column_Total = 0
Count_Zero = 0
For I = 1 to Vertical_Size_Tableau
Current_value = Tableau[I][J]
Column_Total = Column_Total + Current_value
If Current_value = 0 Then
Count_Zero = Count_Zero + 1
EndIf
If Current_value = 1 Then
Here_Found_One = I
EndIf
EndFor
If Count_Zero = (Vertical_Size_Tableau-1) Then
If Column_Total = 1 Then
RESULT_VALUE = Tableau[Here_Found_One][Horizontal_Size_Tableau]
EndIf
Else
RESULT_VALUE = 0
EndIf
Display_cell=math.Round(RESULT_VALUE*100)*RESULT_MULTIPLIER[J]
Display_cell=Display_cell/100
SOLUTION[J]=Display_cell
If SHOW_RESULT[J] = "True" Then
TextWindow.WriteLine(COLUMN_NAME[J]+" ("+COLUMN_FULL_NAME[J]+") = "+ Display_cell)
EndIf
EndFor
' =======================================
' EXPLICITLY SHOW PROTEIN AND FAT CONTENT
' IN EACH BAR
' =======================================
For I = 1 to 2
TextWindow.Write(Constraint_description[I])
TextWindow.Write(" = ")
TextWindow.Write(Constraint[I][4])
TextWindow.Write(" - ACTUAL CONTENT OF ONE BAR = ")
ActualContent = 0
For J = 1 To 3
' Divided by 10 - requirements are in grams, results are in 10 gram servings
ActualContent=ActualContent+Constraint[I][J]*SOLUTION[J]/Serving_Size
EndFor
TextWindow.WriteLine(ActualContent)
EndFor
TextWindow.WriteLine("")
TextWindow.WriteLine("==============================================")
TextWindow.WriteLine(" INITIAL DATA ABOUT INGREDIENTS")
TextWindow.WriteLine("==============================================")
TextWindow.WriteLine("----------------------------------")
TextWindow.WriteLine("CONTENTS OF 10 GRAMS OF INGREDIENT")
TextWindow.WriteLine("----------------------------------")
TextWindow.WriteLine("PEANUT BUTTER, Proteins 2.5g (Ppb) - Fat 5g(Fpb)")
TextWindow.WriteLine("OATS, Proteins 1.7g (Po) - Fat 0.7g (Fo)")
TextWindow.WriteLine("CRANBERRIES, Proteins 0g (Pc)- Fat 0.1g (Fc)")
TextWindow.WriteLine("")
TextWindow.WriteLine("--------------------------------------------")
TextWindow.WriteLine("COST OF 10 GRAMS (one serving) OF INGREDIENT")
TextWindow.WriteLine("--------------------------------------------")
TextWindow.WriteLine("PEANUT BUTTER, 6 cent (Cp)")
TextWindow.WriteLine("OATS, 1 cent (Co)")
TextWindow.WriteLine("CRANBERRIES, 2 cent (Cc)")
TextWindow.WriteLine("")
TextWindow.WriteLine("==============================================")
TextWindow.WriteLine(" FORMAL DESCRIPTION OF THE PROBLEM")
TextWindow.WriteLine("==============================================")
TextWindow.WriteLine(" MINIMIZE COST = 6Cp + 1Co + 2Cc")
TextWindow.WriteLine(" Subject to:")
TextWindow.WriteLine(" 2.5Ppb + 1.7Po + 0Pc >= 10 (at least 10g of protein)")
TextWindow.WriteLine(" 5Ppb + 0.7Po + 0.1Pc <= 14 (no more than 14g of fat)")
TextWindow.WriteLine(" Ppb >= 1.5 (at least 15g of Peanut Butter)")
TextWindow.WriteLine(" Po >= 1.5 (at least 15g of Oats)")
TextWindow.WriteLine(" Pc >= 1.5 (at least 15g of Cranberries)")
TextWindow.WriteLine("==============================================")
TextWindow.WriteLine(" INTERPRETING THE SOLUTION")
TextWindow.WriteLine("==============================================")
TextWindow.WriteLine("HOW COULD I FIND THE SOLUTIONS FOR EACH BASIC VARIABLE?")
TextWindow.WriteLine("At the end of the process, the basic variables for which a")
TextWindow.WriteLine("solution is provided have a single 1 and all zeroes in their")
TextWindow.WriteLine("column. The solution is in the BETA column, in the row that")
TextWindow.WriteLine("contains a 1 in the basic variable column.")
TextWindow.WriteLine("COST (COLUMN BETA, LINE C) = 15.6765")
TextWindow.WriteLine("PARTS OF X = PEANUT BUTTER (COLUMN BETA, LINE S3) Ppb = 1.5 servings (15 grams)")
TextWindow.WriteLine("PARTS OF Y = OATS (COLUMN BETA, LINE S4) Po = 3.67647 servings (36,8 grams)")
TextWindow.WriteLine("PARTS OF Z = CRANBERRIES (COLUMN BETA, LINE S5) Pc = 1.5 servings (15 grams)")
TextWindow.WriteLine("")
TextWindow.WriteLine("Interpreting that result, the minimum cost to produce")
TextWindow.WriteLine("the bar will be about 15 cents, by using 15 grams of")
TextWindow.WriteLine("peanut butter, 36.8 grams of oats, and 15 grams of ")
TextWindow.WriteLine("dried cranberries. Verifying our conditions, we can")
TextWindow.WriteLine("see that our recipe contains at least 15g of each")
TextWindow.WriteLine("ingredient. The bar will weight 15 + 15 + 36.8 = around 66.8 grams")
TextWindow.WriteLine("To check the protein content, we can remember that (as original input")
TextWindow.WriteLine("in the first tableau) protein content for 10 grams is 2.5 (peanut butter)")
TextWindow.WriteLine("and 1.7 (oats), so that the protein content will be around 10g")
TextWindow.WriteLine("(2.5*1.5)+(1.7*3.68)+(0*1.5)")
TextWindow.WriteLine("Fat content for 10 grams of peanut butter, oats and cranberries is respectively")
TextWindow.WriteLine("5 , 0.7 and 0.1, then the fat content will be around 10.15g")
TextWindow.WriteLine("(5*1.5)+(0.7*3.68)+(0.1*1.5)")
TextWindow.WriteLine("")
TextWindow.WriteLine("")
TextWindow.WriteLine("Press any key to terminate the program")
TextWindow.Read()
Program.End()
'========================================================================
'========================================================================
'========================================================================
'========================================================================
Sub ShowSimplexTableau
TextWindow.Clear()
TextWindow.WriteLine("===============================================================================")
TextWindow.WriteLine(" TABLEAU "+TABLEAU_NUMBER+" (One row per constraint, one column per ingredient)")
TextWindow.WriteLine(" X=Peanut butter, Y=Oats, Z=Cranberries")
TextWindow.WriteLine(" In the initial tableau, Columns X, Y, Z in Constraint 1 and 2 show the content")
TextWindow.WriteLine(" in grams of proteins and fats for each ingredient")
TextWindow.WriteLine(" COLUMN BETA, CONSTRAINT 1 is 'PROTEIN CONTENT' (at least 10 grams)")
TextWindow.WriteLine(" COLUMN BETA, CONSTRAINT 2 is 'FAT CONTENT' (no more than 14 grams)")
TextWindow.WriteLine(" COLUMN BETA, CONSTRAINT 3 is 'AT LEAST 1,5 servings OF PEANUT BUTTER' (at list 15 grams)")
TextWindow.WriteLine(" COLUMN BETA, CONSTRAINT 4 is 'AT LEAST 1,5 servings OF OATS' (at list 15 grams)")
TextWindow.WriteLine(" COLUMN BETA, CONSTRAINT 5 is 'AT LEAST 1,5 servings OF DRIED CRANBERRIES' (at list 15 grams)")
TextWindow.WriteLine(" In the initial tableau, Columns X, Y, Z in Constraint 3, 4 and 5 show a 1 flag that")
TextWindow.WriteLine(" refers to the number of servings in the rightmost column")
TextWindow.WriteLine(" Column C refers to the OBJECTIVE FUNCTION VALUE (COST OF A BAR)")
TextWindow.WriteLine(" Bottom line C, columns X, Y, Z refers to the COST OF ONE SERVING OF INGREDIENT")
TextWindow.WriteLine(" The Beta column will contain optimal solutions for the basic variables")
TextWindow.WriteLine("===============================================================================")
TextWindow.Write(" | |")
For J = 1 To Horizontal_Size_Tableau
add_to_line=COLUMN_NAME[J]
swap = "True"
Retry1:
If Text.GetLength(add_to_line) < 10 then
Pad_alternately()
Goto Retry1
EndIf
TextWindow.Write(add_to_line+"|")
EndFor
TextWindow.Write(CRLF)
TextWindow.Write(CRLF)
For I = 1 To Vertical_Size_Tableau
add_to_line=STARRED[I]
swap = "True"
Retry2:
If Text.GetLength(add_to_line) < 15 then
Pad_alternately()
Goto Retry2
EndIf
TextWindow.Write(add_to_line+"|")
add_to_line = COLUMN_NAME[I+3]
swap = "True"
Retry3:
If Text.GetLength(add_to_line) < 10 then
Pad_alternately()
Goto Retry3
EndIf
TextWindow.Write(add_to_line+"|")
For J = 1 To Horizontal_Size_Tableau
Display_cell=math.Round(Tableau[I][J]*100)
add_to_line=Display_cell/100
swap = "True"
Retry4:
If Text.GetLength(add_to_line) < 10 then
Pad_alternately()
Goto Retry4
EndIf
If Already_Pivoted[J] Then
TextWindow.ForegroundColor="Yellow"
Else
TextWindow.ForegroundColor="White"
EndIf
TextWindow.Write(add_to_line)
TextWindow.ForegroundColor="White"
TextWindow.Write("|")
EndFor
TextWindow.Write(CRLF)
EndFor
TextWindow.Write(CRLF)
TextWindow.Write(" Column pivoted? |")
For J = 1 To Horizontal_Size_Tableau
If Already_Pivoted[J] Then
TextWindow.ForegroundColor="Yellow"
TextWindow.Write(" Y ")
TextWindow.ForegroundColor="White"
TextWindow.Write("|")
Else
TextWindow.ForegroundColor="White"
TextWindow.Write(" N |")
EndIf
EndFor
TextWindow.Write(CRLF)
TextWindow.WriteLine(" ")
TextWindow.WriteLine(" PRESS ENTER FOR NEXT STEP")
TextWindow.Read()
EndSub
Sub Pad_alternately
If swap = "True" Then
add_to_line=add_to_line+" "
swap = "False"
else
add_to_line=" "+add_to_line
swap = "True"
EndIf
EndSub